MPRI - Parisian Master of Research in Computer Science <br />Course 2.11.1: Approximation Algorithms, Randomization & Nature Programming <br />Nicolas SCHABANEL, CNRS - Université Paris Diderot <br /> <br />LECTURE 7 (2016/11/9) <br />NATURE PROGRAMMING: INTRINSIC UNIVERSALITY & OTHER MODELS INCLUDING ORITATAMI <br /> <br />[0:00:00] 0. Theory vs Practice <br />[0:04:59] 1. Intrinsic Universality of Tile Assembly Systems at T°=2 <br />[0:39:20] 2. One (Polygonal) Tile is Enough! <br />[0:43:00] 3. Other Models: Bio-Logical Circuits <br />[0:49:43] 4. Nubots: a Model for Molecular Reconfiguration <br />[0:54:07] 5. About Experiments: Nanotubes that Compute <br />[0:58:26] 6. Oritatatami: one Molecule that computes co-transcriptionally <br />[0:58:54] 6.1 Experiment: Synthetic RNA Co-Transcriptional Folding-based Meshes <br />[1:11:58] 6.2 Oritatami: A Model for Co-Transcriptional Folding <br />[1:18:02] 6.3 Oritatami: How to Compute? <br />[1:31:55] 6.4 Oritatami: Rule Design is NP-hard but Fixed Parameter Tractable <br />[1:41:20] 6.5 Oritatami Systems simulate efficiently Turing machines <br />[2:04:36] 6.6 Oritatami: How to Prove the Correctness? <br />[2:28:48] 6.7 Oritatami: Conclusion
